﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Problems.Topsort;
using Algoritmia.Utils;

namespace Algoritmia.Problems.ShortestPaths.Acyclic
{
    public class DagShortestPathsFinder<T> : IShortestPathsFinder<T,double>
    {
        private readonly Func<IDigraph<T>, ITopsorter<T>> _createTopsorter;
        private readonly Func<IEnumerable<T>, IMap<T, double>> _createMap;

        public DagShortestPathsFinder(Func<IDigraph<T>,ITopsorter<T>> createTopsorter = null,
                                     Func<IEnumerable<T>,IMap<T,double>> createMap = null)
        {
            _createTopsorter = createTopsorter ?? (g => new Topsorter<T>());
            _createMap = createMap ?? (g => AlgoritmiaFactory.Maps<T,double>.Default);
        }

        public IEnumerable<KeyValuePair<T, T>> SomeToSomeBackpointers(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var mem = _createMap(g.V);
            var targetsList = targets.ToList();
            var sourcesList = sources.ToList();
            var left = targetsList.Count;
            foreach (var vertex in _createTopsorter(g).Topsort(g))
            {
                if (left == 0) break;
                var v = vertex;

                T u = default(T);
                try
                {
                    u = g.Predecessors(vertex).ArgMin(e => mem[e] + d(e, v));
                    mem[vertex] = mem[u] + d(u, v);
                }
                catch (InvalidOperationException)
                {
                    mem[vertex] = double.PositiveInfinity;
                }
               
                if (sourcesList.Contains(vertex))
                {
                    mem[vertex] = 0.0;
                    u = v;
                }
                yield return new KeyValuePair<T, T>(v,u);
                if (targetsList.Contains(vertex))
                {
                    left--;
                }
            }

        }


        public double SomeToSomeDistance(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            double minDistance = double.PositiveInfinity;
            var mem = _createMap(g.V);
            var targetsList = targets.ToList();
            var left = targetsList.Count;

            foreach (var vertex in _createTopsorter(g).Topsort(g))
            {
                if (left == 0) break;
                var v = vertex;
                mem[vertex] = sources.Contains(vertex)
                                  ? 0.0
                                  : (from u in g.Predecessors(vertex)
                                     select mem[u] + d(u, v)).DefaultIfEmpty(double.PositiveInfinity).Min();
                if (targetsList.Contains(vertex))
                {
                    if (minDistance > mem[vertex])
                    {
                        minDistance = mem[vertex];
                    }
                    left--;
                }
            }
            return minDistance; 

        }
    }
}
